/*
 *https://leetcode.cn/problems/longest-increasing-subsequence/description/
 *300. 最长递增子序列
 *medium, 吴朝泽 2024.9.2
 *动态规划
外层循环 for(int i = 0; i < n; i++) 遍历数组中的每个元素。
dp[i] = 1; 初始化 dp[i] 为 1，因为每个元素自身至少可以构成一个长度为 1 的递增子序列。
内层循环 for(int j = 0; j < i; j++) 遍历当前元素 nums[i] 之前的所有元素。
if(nums[j] < nums[i]) 检查 nums[j] 是否小于 nums[i]。如果是，则 nums[i] 可以在以 nums[j] 结尾的递增子序列之后添加。
dp[i] = max(dp[i], dp[j] + 1); 更新 dp[i]，将 dp[j] + 1（即以 nums[j] 结尾的递增子序列长度加 1）与当前 dp[i] 取最大值。
 */

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int dp[10001] = {0};
        for(int i = 0; i < n; i++)
        {
            dp[i] = 1;
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }    
            }
        }
        int ans = 0;
        for(int i = 0; i < n; i++)
            ans = max(ans,dp[i]);
        return ans;
    }
};